package com.xyhuo.leetcode.december;

/**
 * 寻找峰值Ⅱ
 * https://leetcode.cn/problems/find-a-peak-element-ii/
 *
 * @time 2023/12/19
 */
public class FindPeakGrid {

//    public static void main(String[] args) {
//        FindPeakGrid fpg = new FindPeakGrid();
////        int[][] mat = {{1, 4}, {3, 2}};
//        int[][] mat = {{10, 20, 15}, {21, 30, 14}, {7, 16, 32}};
//        int[] peakGrid = fpg.findPeakGrid(mat);
//        System.out.println(peakGrid[0] + " " + peakGrid[1]);
//    }

    public int[] findPeakGrid(int[][] mat) {
        for (int i = 0; i < mat.length; i++) {
            if (findAns) {
                break;
            }
            findPeak(mat, i, 0, mat[i].length - 1);
        }
        return new int[]{x, y};
    }

    private boolean findAns = false;

    private int x;
    private int y;

    private void findPeak(int[][] mat, int index, int left, int right) {
        if (left >= right || findAns) {
            return;
        }

        int middle = (left + right) / 2;
        Integer rowIndex = null;
        int n = mat[index].length;
        if ((left + 1 <= right && mat[index][left] > mat[index][left + 1])
                && ((left > 0 && mat[index][left] > mat[index][left - 1]) || left == 0)) {
            rowIndex = left;
        } else if (right - 1 >= left && mat[index][right] > mat[index][right - 1]
                && (right == n - 1 || (right + 1 < n && mat[index][right] > mat[index][right + 1]))) {
            rowIndex = right;
        } else if (mat[index][middle] > mat[index][left] && mat[index][middle] > mat[index][right]) {
            while (middle + 1 < n && mat[index][middle] < mat[index][middle + 1]) {
                middle++;
            }
            while (middle - 1 < n && mat[index][middle] < mat[index][middle - 1]) {
                middle--;
            }
            rowIndex = middle;
        }
        if (rowIndex != null) {
            boolean verify = true;
            if (index - 1 >= 0 && mat[index - 1][rowIndex] >= mat[index][rowIndex]) {
                verify = false;
            }
            if (index + 1 < mat.length && mat[index + 1][rowIndex] >= mat[index][rowIndex]) {
                verify = false;
            }
            if (verify) {
                findAns = true;
                x = index;
                y = rowIndex;
            }
        }
        if (middle != right) {
            findPeak(mat, index, left, middle);
        }

        if (middle != left) {
            findPeak(mat, index, middle, right);
        }

    }
}
